{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def range_matrix(r,c):\n",
    "    return np.arange(r*c).reshape((r, c))*0.1+0.1\n",
    "\n",
    "\n",
    "input_len = 3\n",
    "num_classes = 3\n",
    "n, p = 0, 0\n",
    "hidden_size = 2 # size of hidden layer of neurons\n",
    "seq_length = 3 # number of steps to unroll the RNN for\n",
    "learning_rate = 1\n",
    "\n",
    "data_len = 50000\n",
    "x = np.arange(data_len)+1\n",
    "\n",
    "ground_truth = [(x[i-1] + x[i-2]) % 3 for i in range(data_len)]\n",
    "\n",
    "# model parameters\n",
    "U = range_matrix(hidden_size, input_len) # input to hidden\n",
    "W = range_matrix(hidden_size, hidden_size) # hidden to hidden\n",
    "V = range_matrix(num_classes, hidden_size) # hidden to output\n",
    "bs = np.zeros((hidden_size, 1)) # hidden bias\n",
    "bo = np.zeros((num_classes, 1)) # output bias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.shape(U)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "完成下面的函数，将代码填写到\n",
    "`'''Fill your code HERE'''`的地方"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forward_and_backprop(inputs, targets, hprev):\n",
    "  xs, hs, ys, ps = {}, {}, {}, {}\n",
    "  hs[-1] = np.copy(hprev)\n",
    "  loss = 0\n",
    "  # forward pass\n",
    "  for t in range(seq_length):\n",
    "    xs[t] = inputs[t:t+3].reshape(input_len, 1) # make a matrix(rank 2)\n",
    "    hs[t] = np.tanh(np.dot(W,hs[t-1]) + np.dot(U,xs[t]) + bs) #计算hidden state。激活函数使用tanh\n",
    "    ys[t] = np.dot(V,hs[t]) + bo #计算output logits。注意这里没有激活函数，我们将在下一步计算softmax\n",
    "    print('xs:',xs)\n",
    "    print('hs:',hs)\n",
    "    print('ys:',ys)\n",
    "    ps[t] = np.exp(ys[t]) / np.sum(np.exp(ys[t])) # softmax\n",
    "    print('ps:',ps)\n",
    "    print('ps[t]:',ps[t])\n",
    "    print('targets:',targets[t])\n",
    "    loss = loss - np.log(ps[t][targets[t]]) # 计算交叉熵\n",
    "    \n",
    "  #反向传播过程  \n",
    "  dU, dW, dV = np.zeros_like(U), np.zeros_like(W), np.zeros_like(V)\n",
    "  dbs, dbo = np.zeros_like(bs), np.zeros_like(bo)\n",
    "  dhnext = np.zeros_like(hs[0])\n",
    "\n",
    "  \n",
    "  for t in reversed(range(seq_length)):\n",
    "    dy = np.copy(ps[t])\n",
    "    dy[targets[t]] -= 1 # softmax-交叉熵delta： y-t\n",
    "    dV = dV + np.dot(dy,hs[t].T) #V-nabla\n",
    "    dbo = dbo + dy #bo-nabla\n",
    "    dh = np.dot(W.T,dhnext) + np.dot(V.T,dy) # backprop into hidden-state\n",
    "    dhraw = (1 - hs[t] * hs[t]) * dh # tanh的导数是1-logits^2\n",
    "    dbs = dbs + dhraw #bs-nabla\n",
    "    dU = dU + np.dot(dhraw,xs[t].T) # U-nabla\n",
    "    if t>0:\n",
    "      dW = dW + np.dot(dhraw, hs[t-1].T) # W-nabla\n",
    "    dhnext = dhraw\n",
    "   \n",
    "    \n",
    "  return loss, dU, dW, dV, dbs, dbo, hs[seq_length-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "执行前向+反向传播5次（每次计算的time step为3）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "inputs: [1 2 3 4 5]\n",
      "xs: {0: array([[1],\n",
      "       [2],\n",
      "       [3]])}\n",
      "hs: {-1: array([[0.],\n",
      "       [0.]]), 0: array([[0.88535165],\n",
      "       [0.9966824 ]])}\n",
      "ys: {0: array([[0.28787164],\n",
      "       [0.66427845],\n",
      "       [1.04068526]])}\n",
      "ps: {0: array([[0.21834039],\n",
      "       [0.31813063],\n",
      "       [0.46352898]])}\n",
      "ps[t]: [[0.21834039]\n",
      " [0.31813063]\n",
      " [0.46352898]]\n",
      "targets: 0\n",
      "xs: {0: array([[1],\n",
      "       [2],\n",
      "       [3]]), 1: array([[2],\n",
      "       [3],\n",
      "       [4]])}\n",
      "hs: {-1: array([[0.],\n",
      "       [0.]]), 0: array([[0.88535165],\n",
      "       [0.9966824 ]]), 1: array([[0.97961268],\n",
      "       [0.99995618]])}\n",
      "ys: {0: array([[0.28787164],\n",
      "       [0.66427845],\n",
      "       [1.04068526]]), 1: array([[0.2979525 ],\n",
      "       [0.69386628],\n",
      "       [1.08978005]])}\n",
      "ps: {0: array([[0.21834039],\n",
      "       [0.31813063],\n",
      "       [0.46352898]]), 1: array([[0.21307568],\n",
      "       [0.31657532],\n",
      "       [0.470349  ]])}\n",
      "ps[t]: [[0.21307568]\n",
      " [0.31657532]\n",
      " [0.470349  ]]\n",
      "targets: 2\n",
      "xs: {0: array([[1],\n",
      "       [2],\n",
      "       [3]]), 1: array([[2],\n",
      "       [3],\n",
      "       [4]]), 2: array([[3],\n",
      "       [4],\n",
      "       [5]])}\n",
      "hs: {-1: array([[0.],\n",
      "       [0.]]), 0: array([[0.88535165],\n",
      "       [0.9966824 ]]), 1: array([[0.97961268],\n",
      "       [0.99995618]]), 2: array([[0.99393847],\n",
      "       [0.99999794]])}\n",
      "ys: {0: array([[0.28787164],\n",
      "       [0.66427845],\n",
      "       [1.04068526]]), 1: array([[0.2979525 ],\n",
      "       [0.69386628],\n",
      "       [1.08978005]]), 2: array([[0.29939344],\n",
      "       [0.69818072],\n",
      "       [1.096968  ]])}\n",
      "ps: {0: array([[0.21834039],\n",
      "       [0.31813063],\n",
      "       [0.46352898]]), 1: array([[0.21307568],\n",
      "       [0.31657532],\n",
      "       [0.470349  ]]), 2: array([[0.21230673],\n",
      "       [0.31634056],\n",
      "       [0.4713527 ]])}\n",
      "ps[t]: [[0.21230673]\n",
      " [0.31634056]\n",
      " [0.4713527 ]]\n",
      "targets: 1\n",
      "inputs: [4 5 6 7 8]\n",
      "xs: {0: array([[4],\n",
      "       [5],\n",
      "       [6]])}\n",
      "hs: {-1: array([[0.99393847],\n",
      "       [0.99999794]]), 0: array([[0.96298929],\n",
      "       [0.99999989]])}\n",
      "ys: {0: array([[ 1.26848421],\n",
      "       [ 0.87236114],\n",
      "       [-0.07415513]])}\n",
      "ps: {0: array([[0.51704187],\n",
      "       [0.34792982],\n",
      "       [0.13502832]])}\n",
      "ps[t]: [[0.51704187]\n",
      " [0.34792982]\n",
      " [0.13502832]]\n",
      "targets: 0\n",
      "xs: {0: array([[4],\n",
      "       [5],\n",
      "       [6]]), 1: array([[5],\n",
      "       [6],\n",
      "       [7]])}\n",
      "hs: {-1: array([[0.99393847],\n",
      "       [0.99999794]]), 0: array([[0.96298929],\n",
      "       [0.99999989]]), 1: array([[0.98035053],\n",
      "       [0.99999999]])}\n",
      "ys: {0: array([[ 1.26848421],\n",
      "       [ 0.87236114],\n",
      "       [-0.07415513]]), 1: array([[ 1.27494772],\n",
      "       [ 0.87909278],\n",
      "       [-0.07172503]])}\n",
      "ps: {0: array([[0.51704187],\n",
      "       [0.34792982],\n",
      "       [0.13502832]]), 1: array([[0.51727476],\n",
      "       [0.34817988],\n",
      "       [0.13454536]])}\n",
      "ps[t]: [[0.51727476]\n",
      " [0.34817988]\n",
      " [0.13454536]]\n",
      "targets: 2\n",
      "xs: {0: array([[4],\n",
      "       [5],\n",
      "       [6]]), 1: array([[5],\n",
      "       [6],\n",
      "       [7]]), 2: array([[6],\n",
      "       [7],\n",
      "       [8]])}\n",
      "hs: {-1: array([[0.99393847],\n",
      "       [0.99999794]]), 0: array([[0.96298929],\n",
      "       [0.99999989]]), 1: array([[0.98035053],\n",
      "       [0.99999999]]), 2: array([[0.98971495],\n",
      "       [1.        ]])}\n",
      "ys: {0: array([[ 1.26848421],\n",
      "       [ 0.87236114],\n",
      "       [-0.07415513]]), 1: array([[ 1.27494772],\n",
      "       [ 0.87909278],\n",
      "       [-0.07172503]]), 2: array([[ 1.27843403],\n",
      "       [ 0.88272371],\n",
      "       [-0.07041428]])}\n",
      "ps: {0: array([[0.51704187],\n",
      "       [0.34792982],\n",
      "       [0.13502832]]), 1: array([[0.51727476],\n",
      "       [0.34817988],\n",
      "       [0.13454536]]), 2: array([[0.51739999],\n",
      "       [0.34831454],\n",
      "       [0.13428547]])}\n",
      "ps[t]: [[0.51739999]\n",
      " [0.34831454]\n",
      " [0.13428547]]\n",
      "targets: 1\n",
      "inputs: [ 7  8  9 10 11]\n",
      "xs: {0: array([[7],\n",
      "       [8],\n",
      "       [9]])}\n",
      "hs: {-1: array([[0.98971495],\n",
      "       [1.        ]]), 0: array([[0.97228697],\n",
      "       [1.        ]])}\n",
      "ys: {0: array([[-0.37023718],\n",
      "       [ 0.75658006],\n",
      "       [ 1.68871539]])}\n",
      "ps: {0: array([[0.08386746],\n",
      "       [0.25879984],\n",
      "       [0.6573327 ]])}\n",
      "ps[t]: [[0.08386746]\n",
      " [0.25879984]\n",
      " [0.6573327 ]]\n",
      "targets: 0\n",
      "xs: {0: array([[7],\n",
      "       [8],\n",
      "       [9]]), 1: array([[ 8],\n",
      "       [ 9],\n",
      "       [10]])}\n",
      "hs: {-1: array([[0.98971495],\n",
      "       [1.        ]]), 0: array([[0.97228697],\n",
      "       [1.        ]]), 1: array([[0.98217418],\n",
      "       [1.        ]])}\n",
      "ys: {0: array([[-0.37023718],\n",
      "       [ 0.75658006],\n",
      "       [ 1.68871539]]), 1: array([[-0.3720348 ],\n",
      "       [ 0.76010316],\n",
      "       [ 1.6958884 ]])}\n",
      "ps: {0: array([[0.08386746],\n",
      "       [0.25879984],\n",
      "       [0.6573327 ]]), 1: array([[0.08325934],\n",
      "       [0.25829396],\n",
      "       [0.65844669]])}\n",
      "ps[t]: [[0.08325934]\n",
      " [0.25829396]\n",
      " [0.65844669]]\n",
      "targets: 2\n",
      "xs: {0: array([[7],\n",
      "       [8],\n",
      "       [9]]), 1: array([[ 8],\n",
      "       [ 9],\n",
      "       [10]]), 2: array([[ 9],\n",
      "       [10],\n",
      "       [11]])}\n",
      "hs: {-1: array([[0.98971495],\n",
      "       [1.        ]]), 0: array([[0.97228697],\n",
      "       [1.        ]]), 1: array([[0.98217418],\n",
      "       [1.        ]]), 2: array([[0.98861502],\n",
      "       [1.        ]])}\n",
      "ys: {0: array([[-0.37023718],\n",
      "       [ 0.75658006],\n",
      "       [ 1.68871539]]), 1: array([[-0.3720348 ],\n",
      "       [ 0.76010316],\n",
      "       [ 1.6958884 ]]), 2: array([[-0.37320584],\n",
      "       [ 0.76239821],\n",
      "       [ 1.70056114]])}\n",
      "ps: {0: array([[0.08386746],\n",
      "       [0.25879984],\n",
      "       [0.6573327 ]]), 1: array([[0.08325934],\n",
      "       [0.25829396],\n",
      "       [0.65844669]]), 2: array([[0.08286525],\n",
      "       [0.25796393],\n",
      "       [0.65917082]])}\n",
      "ps[t]: [[0.08286525]\n",
      " [0.25796393]\n",
      " [0.65917082]]\n",
      "targets: 1\n",
      "inputs: [10 11 12 13 14]\n",
      "xs: {0: array([[10],\n",
      "       [11],\n",
      "       [12]])}\n",
      "hs: {-1: array([[0.98861502],\n",
      "       [1.        ]]), 0: array([[-0.99999951],\n",
      "       [ 1.        ]])}\n",
      "ys: {0: array([[ 0.76132051],\n",
      "       [ 0.27541206],\n",
      "       [-0.73673212]])}\n",
      "ps: {0: array([[0.54386156],\n",
      "       [0.33454998],\n",
      "       [0.12158846]])}\n",
      "ps[t]: [[0.54386156]\n",
      " [0.33454998]\n",
      " [0.12158846]]\n",
      "targets: 0\n",
      "xs: {0: array([[10],\n",
      "       [11],\n",
      "       [12]]), 1: array([[11],\n",
      "       [12],\n",
      "       [13]])}\n",
      "hs: {-1: array([[0.98861502],\n",
      "       [1.        ]]), 0: array([[-0.99999951],\n",
      "       [ 1.        ]]), 1: array([[-0.99999992],\n",
      "       [ 1.        ]])}\n",
      "ys: {0: array([[ 0.76132051],\n",
      "       [ 0.27541206],\n",
      "       [-0.73673212]]), 1: array([[ 0.76132028],\n",
      "       [ 0.27541182],\n",
      "       [-0.73673203]])}\n",
      "ps: {0: array([[0.54386156],\n",
      "       [0.33454998],\n",
      "       [0.12158846]]), 1: array([[0.54386154],\n",
      "       [0.33454996],\n",
      "       [0.1215885 ]])}\n",
      "ps[t]: [[0.54386154]\n",
      " [0.33454996]\n",
      " [0.1215885 ]]\n",
      "targets: 2\n",
      "xs: {0: array([[10],\n",
      "       [11],\n",
      "       [12]]), 1: array([[11],\n",
      "       [12],\n",
      "       [13]]), 2: array([[12],\n",
      "       [13],\n",
      "       [14]])}\n",
      "hs: {-1: array([[0.98861502],\n",
      "       [1.        ]]), 0: array([[-0.99999951],\n",
      "       [ 1.        ]]), 1: array([[-0.99999992],\n",
      "       [ 1.        ]]), 2: array([[-0.99999998],\n",
      "       [ 1.        ]])}\n",
      "ys: {0: array([[ 0.76132051],\n",
      "       [ 0.27541206],\n",
      "       [-0.73673212]]), 1: array([[ 0.76132028],\n",
      "       [ 0.27541182],\n",
      "       [-0.73673203]]), 2: array([[ 0.76132025],\n",
      "       [ 0.27541178],\n",
      "       [-0.73673201]])}\n",
      "ps: {0: array([[0.54386156],\n",
      "       [0.33454998],\n",
      "       [0.12158846]]), 1: array([[0.54386154],\n",
      "       [0.33454996],\n",
      "       [0.1215885 ]]), 2: array([[0.54386154],\n",
      "       [0.33454996],\n",
      "       [0.1215885 ]])}\n",
      "ps[t]: [[0.54386154]\n",
      " [0.33454996]\n",
      " [0.1215885 ]]\n",
      "targets: 1\n",
      "inputs: [13 14 15 16 17]\n",
      "xs: {0: array([[13],\n",
      "       [14],\n",
      "       [15]])}\n",
      "hs: {-1: array([[-0.99999998],\n",
      "       [ 1.        ]]), 0: array([[-1.],\n",
      "       [ 1.]])}\n",
      "ys: {0: array([[-1.13343384],\n",
      "       [ 0.26446227],\n",
      "       [ 1.16897158]])}\n",
      "ps: {0: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]])}\n",
      "ps[t]: [[0.06646779]\n",
      " [0.2689737 ]\n",
      " [0.66455851]]\n",
      "targets: 0\n",
      "xs: {0: array([[13],\n",
      "       [14],\n",
      "       [15]]), 1: array([[14],\n",
      "       [15],\n",
      "       [16]])}\n",
      "hs: {-1: array([[-0.99999998],\n",
      "       [ 1.        ]]), 0: array([[-1.],\n",
      "       [ 1.]]), 1: array([[-1.],\n",
      "       [ 1.]])}\n",
      "ys: {0: array([[-1.13343384],\n",
      "       [ 0.26446227],\n",
      "       [ 1.16897158]]), 1: array([[-1.13343385],\n",
      "       [ 0.26446226],\n",
      "       [ 1.16897158]])}\n",
      "ps: {0: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]]), 1: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]])}\n",
      "ps[t]: [[0.06646779]\n",
      " [0.2689737 ]\n",
      " [0.66455851]]\n",
      "targets: 2\n",
      "xs: {0: array([[13],\n",
      "       [14],\n",
      "       [15]]), 1: array([[14],\n",
      "       [15],\n",
      "       [16]]), 2: array([[15],\n",
      "       [16],\n",
      "       [17]])}\n",
      "hs: {-1: array([[-0.99999998],\n",
      "       [ 1.        ]]), 0: array([[-1.],\n",
      "       [ 1.]]), 1: array([[-1.],\n",
      "       [ 1.]]), 2: array([[-1.],\n",
      "       [ 1.]])}\n",
      "ys: {0: array([[-1.13343384],\n",
      "       [ 0.26446227],\n",
      "       [ 1.16897158]]), 1: array([[-1.13343385],\n",
      "       [ 0.26446226],\n",
      "       [ 1.16897158]]), 2: array([[-1.13343385],\n",
      "       [ 0.26446226],\n",
      "       [ 1.16897158]])}\n",
      "ps: {0: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]]), 1: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]]), 2: array([[0.06646779],\n",
      "       [0.2689737 ],\n",
      "       [0.66455851]])}\n",
      "ps[t]: [[0.06646779]\n",
      " [0.2689737 ]\n",
      " [0.66455851]]\n",
      "targets: 1\n",
      "U:\n",
      "[[-0.24492589 -0.23727184 -0.2296178 ]\n",
      " [ 0.39838373  0.49675484  0.59512595]]\n",
      "W:\n",
      "[[0.0992239  0.19968422]\n",
      " [0.3000113  0.40001275]]\n",
      "V:\n",
      "[[ 0.37622149  0.920997  ]\n",
      " [ 0.39517001  0.81996845]\n",
      " [ 0.1286085  -0.54096546]]\n"
     ]
    }
   ],
   "source": [
    "for n in range(5):\n",
    "  # prepare inputs (we're sweeping from left to right in steps seq_length long)\n",
    "  if p+seq_length+1 >= len(x) or n == 0: \n",
    "    hprev = np.zeros((hidden_size,1)) # reset RNN memory\n",
    "    p = 2 # go from start of data\n",
    "  inputs =  x[p-2:p+seq_length]\n",
    "  print('inputs:',inputs)\n",
    "  targets = ground_truth[p:p+seq_length]\n",
    "  loss, dU, dW, dV, dbs, dbo, hprev = forward_and_backprop(inputs, targets, hprev)\n",
    "  # perform parameter update with Adagrad\n",
    "  for param, dparam in zip([U, W, V, bs, bo], \n",
    "                                [dU, dW, dV, dbs, dbo]):\n",
    "    param += -learning_rate * dparam #sgd\n",
    "\n",
    "  p += seq_length # move data pointer\n",
    "\n",
    "print('U:')\n",
    "print(U)\n",
    "print('W:')\n",
    "print(W)\n",
    "print('V:')\n",
    "print(V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果一切正确，你应该看到如下的结果：\n",
    "```\n",
    "U:\n",
    "[[-0.24492589 -0.23727184 -0.2296178 ]\n",
    " [ 0.39838373  0.49675484  0.59512595]]\n",
    "W:\n",
    "[[ 0.0992239   0.19968422]\n",
    " [ 0.3000113   0.40001275]]\n",
    "V:\n",
    "[[ 0.37622149  0.920997  ]\n",
    " [ 0.39517001  0.81996845]\n",
    " [ 0.1286085  -0.54096546]]\n",
    "\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
